package code.sort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName RadixSort
 * @Description 基数排序
 * https://blog.csdn.net/afei__/article/details/82971310
 * @Author za-zhouyunxing
 * @Date 2019/10/31 15:29
 * @Version 1.0
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[]{321, 1234, 543, 324, 24, 960, 540, 672, 783, 1000};
        radixSort(arr);
        printArray(arr);
    }

    private static void radixSort(int[] arr) {
        //获取最大数是多少位
        int digit = getMaxDigit(arr);
        for (int i = 0; i < digit ; i++) {
            // 执行 digit 次 bucketSort 排序即可
            bucketSort(arr, i);
        }
    }

    private static void bucketSort(int[] arr, int digit) {
        //自然数范围在0-9，所以创建10个桶
        List<LinkedList<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            buckets.add(new LinkedList<>());
        }
        // sort
        int base = (int)Math.pow(10, digit);
        for (int data : arr) {
            int index = data / base % 10;
            buckets.get(index).add(data);
        }
        //output: copy back to arr
        int index = 0;
        for (LinkedList<Integer> bucket : buckets) {
            for (Integer data : bucket) {
                arr[index++] = data;
            }
        }

    }

    /**
     * 获取最大数是多少位
     * @param arr
     * @return
     */
    private static int getMaxDigit(int[] arr) {
        // 默认只有一位
        int digit = 1;
        // 十进制每多一位，代表其值大了10倍
        int base = 10;
        for (int data : arr) {
            if (data >= base){
                digit++;
                base = base * 10;
            }
        }
        return digit;
    }

    private static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
